9032. Обновление дорог

 

В Берляндии есть n городов, соединённых m двусторонними дорогами. Дороги не могут соединять город с самим собой, и каждая пара городов соединяется не более чем одной дорогой. Не гарантируется, что из любого города можно доехать до любого другого, используя только имеющиеся дороги.

Мер города Гаджи Ибрахим решил внести изменения в систему дорожных путей и дал указание министерству транспорта заняться данной реформой. Теперь каждая дорога должна стать односторонней (вести только из одного города в другой).

Чтобы не вызвать большого недовольства у жителей, необходимо провести реформу так, чтобы оставалось как можно меньше обособленных городов. Город считается обособленным, если в него не входит ни одна дорога, при этом выходящие из этого города дороги допустимы.

Помогите Гаджи Ибрагиму найти минимальное количество обособленных городов после проведения реформы.

 

Вход. Первая строка содержит два натуральных числа n и m (2 ≤ n ≤ 105, 1 ≤ m ≤ 105) – количество городов и дорог в Берляндии.

В следующих m строках содержатся описания дорог: i-я дорога задаётся двумя различными целыми числами xi, yi (1 ≤ xi, yi ≤ n, xi ≠ yi), где xi и yi равны номерам городов, которые соединяет i-я дорога.

Гарантируется, что между каждой парой городов не может быть более одной дороги, но не гарантируется, что из любого города можно доехать до любого другого, используя только имеющиеся дороги.

 

Выход. Выведите одно число – минимальное количество обособленных городов после проведения реформы.

 

Пример входа 1

Пример выхода 1

4 3

2 1

1 3

4 3

1

 

 

Пример входа 2

Пример выхода 2

5 5

2 1

1 3

2 3

2 5

4 3

0

 

 

РЕШЕНИЕ

дерево

 

Анализ алгоритма

Выделим в неориентированном графе компоненты связности. Если компонента связности является деревом (не содержит цикла), то всегда можно ориентировать ребра так, чтобы была в точности одна вершина без исходящих ребер. То есть в компоненте, являющейся деревом, количество обособленных городов после проведения реформы можно сделать минимум 1 (0 сделать нельзя). Например, обособленным городом можно сделать корень дерева:

 

Если в компоненте связности присутствует цикл, то ребра всегда можно ориентировать так, чтобы не существовало вершины без исходящих ребер.

Ответ на задачу равен количеству компонент связности без циклов.

 

Пример

Рассмотрим первый пример. Слева приведен исходный граф. Справа – граф после реформы. Вершина 1 не имеет исходящих ребер.

 

Рассмотрим второй пример. Слева приведен исходный граф. Справа – граф после реформы. Каждая вершина имеет исходящее ребро.

 

Реализация алгоритма

Объявим список смежности g для хранения графа. Объявим массив used для отмечания пройденных вершин.

 

vector<vector<int> > g;

vector<int> used;

 

Функция dfs совершает поиск в глубину из вершины v. Предком вершины v является вершина p.

 

void dfs(int v, int p = -1)

{

  used[v] = 1;

  for (int i = 0; i < g[v].size(); i++)

  {

    int to = g[v][i];

    if (to == p) continue;

 

Если в текущей компоненте связности имеется цикл, то установим flag = 0.

 

    if (used[to] == 1) flag = 0;

    else dfs(to, v);

  }

}

 

Основная часть программы. Читаем входные данные.

 

scanf("%d %d", &n, &m);

g.resize(n + 1);

used.resize(n + 1);

 

Читаем m ребер. Строим граф.

 

for (i = 0; i < m; i++)

{

  scanf("%d %d", &a, &b);

  g[a].push_back(b);

  g[b].push_back(a);

}

 

Запускаем поиск в глубину на несвязном графе. В переменной res подсчитываем количество компонент связности, в которых нет цикла.

 

res = 0;

for (i = 1; i <= n; i++)

{

  if (used[i] == 0)

 

  {

 

Установим изначально flag = 1. Если текущая компонента связности содержит цикл, то после вызова dfs станет flag = 0.

 

    flag = 1;

    dfs(i);

    res += flag;

  }

}

 

Выводим ответ.

 

printf("%d\n", res);